﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
using MLSharp.Utilities;

namespace MLSharp.Clustering
{
	/// <summary>
	/// Builds a cobweb cluster tree.
	/// </summary>
	/// <remarks>
	/// This class was ported from Weka 3.5.
	/// </remarks>
	public class Cobweb
	{
		#region CNode Class

		///<summary>
		///Inner class handling node operations for Cobweb.
		///</summary>
		protected internal class CNode : IProbabilisticClusterNode
		{
			#region Fields

			/// <summary>
			/// Within cluster attribute statistics.
			/// </summary>
			protected internal AttributeStats[] mAttStats;

			/// <summary>
			/// Number of attributes
			/// </summary>
			private readonly int mNumAttributes;

			/// <summary>
			/// Total instances at this node
			/// </summary>
			private double mTotalInstances;

			/// <summary>
			/// The instance of Cobweb that the node belongs to.
			/// </summary>
			private readonly Cobweb mCobweb;

			/// <summary>
			/// Instances at this node
			/// </summary>
			protected List<Instance> mClusterInstances;

			/// <summary>
			/// Children of this node
			/// </summary>
			internal List<CNode> mChildren;

			/// <summary>
			/// Cluster number of this node
			/// </summary>
			internal int mClusterNum = -1;

			#endregion

			#region Constructors

			///<summary>
			///Creates an empty <code>CNode</code> instance
			///</summary>
			///<param name="numAttributes">the number of attributes in the data</param>
			///<param name="cobweb">The instance of Cobweb this node belongs to.</param>
			public CNode(int numAttributes, Cobweb cobweb)
			{
				mNumAttributes = numAttributes;
				mCobweb = cobweb;
			}

			///<summary>
			///Creates a new leaf <code>CNode</code> instance.
			///</summary>
			///<param name="numAttributes">the number of attributes in the data</param>
			///<param name="leafInstance">the instance to store at this leaf</param>
			///<param name="cobweb">The instance of Cobweb this node belongs to.</param>
			public CNode(int numAttributes, Instance leafInstance, Cobweb cobweb)
				: this(numAttributes, cobweb)
			{
				if (mClusterInstances == null)
				{
					mClusterInstances = new List<Instance>();
				}

				mClusterInstances.Add(leafInstance);
				UpdateStats(leafInstance, false);
			}

			#endregion

			#region Public Properties

			/// <summary>
			/// The number of instances in the node.
			/// </summary>
			public int NumInstances
			{
				get { return mClusterInstances.Count; }
			}

			#endregion

			#region  Private Methods

			/// <summary>
			/// Temporarily adds a new instance to each of this nodes children
			/// in turn and computes the category utility.
			/// </summary>
			/// <param name="newInstance">the new instance to evaluate</param>
			/// <returns>an array of category utility values---the result of considering
			/// each child in turn as a host for the new instance</returns>
			private double[] CuScoresForChildren(Instance newInstance)
			{
				// look for a host in existing children
				double[] categoryUtils = new double[mChildren.Count];

				// look for a home for this instance in the existing children
				for (int i = 0; i < mChildren.Count; i++)
				{
					CNode temp = mChildren[i];
					// tentitively add the new instance to this child
					temp.UpdateStats(newInstance, false);
					categoryUtils[i] = CategoryUtility();

					// remove the new instance from this child
					temp.UpdateStats(newInstance, true);
				}
				return categoryUtils;
			}

			/// <summary>
			/// Calculates the Category Utility score for the tree formed by merging the best
			/// two host nodes into a single node.
			/// </summary>
			/// <param name="merged"></param>
			/// <param name="a"></param>
			/// <param name="b"></param>
			/// <param name="newInstance"></param>
			/// <returns></returns>
			private double CuScoreForBestTwoMerged(CNode merged,
							   CNode a, CNode b,
							   Instance newInstance)
			{
				// consider merging the best and second
				// best.
				merged.mClusterInstances = new List<Instance>();

				merged.AddChildNode(a);
				merged.AddChildNode(b);
				merged.UpdateStats(newInstance, false); // add new instance to stats
				// remove the best and second best nodes
				mChildren.Remove(a);
				mChildren.Remove(b);
				mChildren.Add(merged);
				double mergedCU = CategoryUtility();
				// restore the status quo
				merged.UpdateStats(newInstance, true);
				mChildren.Remove(merged);
				mChildren.Add(a);
				mChildren.Add(b);
				return mergedCU;
			}

			#endregion

			#region Internal Methods

			/// <summary>
			/// Finds a host for the new instance in this nodes children. Also
			/// considers merging the two best hosts and splitting the best host.
			/// </summary>
			/// <param name="newInstance">the instance to find a host for</param>
			/// <param name="structureFrozen">true if the instance is not to be added to
			/// the tree and instead the best potential host is to be returned</param>
			/// <returns>the best host</returns>
			internal CNode FindHost(Instance newInstance,
					   bool structureFrozen)
			{
				if (!structureFrozen)
				{
					UpdateStats(newInstance, false);
				}

				// look for a host in existing children and also consider as a new leaf
				double[] categoryUtils = CuScoresForChildren(newInstance);

				// make a temporary new leaf for this instance and get CU
				CNode newLeaf = new CNode(mNumAttributes, newInstance, mCobweb);
				mChildren.Add(newLeaf);
				double bestHostCU = CategoryUtility();
				CNode finalBestHost = newLeaf;

				// remove new leaf when seaching for best and second best nodes to
				// consider for merging and splitting
				mChildren.RemoveAt(mChildren.Count - 1);

				// now determine the best host (and the second best)
				int best = 0;
				int secondBest = 0;
				for (int i = 0; i < categoryUtils.Length; i++)
				{
					if (categoryUtils[i] > categoryUtils[secondBest])
					{
						if (categoryUtils[i] > categoryUtils[best])
						{
							secondBest = best;
							best = i;
						}
						else
						{
							secondBest = i;
						}
					}
				}

				CNode a = mChildren[best];
				CNode b = mChildren[secondBest];
				if (categoryUtils[best] > bestHostCU)
				{
					bestHostCU = categoryUtils[best];
					finalBestHost = a;
					//	System.out.println("Node is best");
				}

				if (structureFrozen)
				{
					if (finalBestHost == newLeaf)
					{
						return null; // *this* node is the best host
					}
					else
					{
						return finalBestHost;
					}
				}

				CNode merged = new CNode(mNumAttributes, mCobweb);
				if (a != b)
				{
					double mergedCU = CuScoreForBestTwoMerged(merged, a, b, newInstance);

					if (mergedCU > bestHostCU)
					{
						bestHostCU = mergedCU;
						finalBestHost = merged;
					}
				}

				// Consider splitting the best
				double splitPlusMergeBestTwoCU = double.MinValue;
				if (a.mChildren != null)
				{
					List<CNode> tempChildren = new List<CNode>();

					for (int i = 0; i < mChildren.Count; i++)
					{
						CNode existingChild = mChildren[i];
						if (existingChild != a)
						{
							tempChildren.Add(existingChild);
						}
					}
					for (int i = 0; i < a.mChildren.Count; i++)
					{
						CNode promotedChild = a.mChildren[i];
						tempChildren.Add(promotedChild);
					}
					// also add the new leaf
					tempChildren.Add(newLeaf);

					List<CNode> saveStatusQuo = mChildren;
					mChildren = tempChildren;
					double splitPlusNewLeafCU = CategoryUtility();
					// remove the new leaf
					tempChildren.RemoveAt(tempChildren.Count - 1);
					// now look for best and second best
					categoryUtils = CuScoresForChildren(newInstance);

					// now determine the best host (and the second best)
					best = 0;
					secondBest = 0;
					for (int i = 0; i < categoryUtils.Length; i++)
					{
						if (categoryUtils[i] > categoryUtils[secondBest])
						{
							if (categoryUtils[i] > categoryUtils[best])
							{
								secondBest = best;
								best = i;
							}
							else
							{
								secondBest = i;
							}
						}
					}
					CNode sa = mChildren[best];
					CNode sb = mChildren[secondBest];
					double splitBestChildCU = categoryUtils[best];

					// now merge best and second best
					CNode mergedSplitChildren = new CNode(mNumAttributes, mCobweb);
					if (sa != sb)
					{
						splitPlusMergeBestTwoCU =
						  CuScoreForBestTwoMerged(mergedSplitChildren, sa, sb, newInstance);
					}
					double splitCU = (splitBestChildCU > splitPlusNewLeafCU) ?
					                                                         	splitBestChildCU : splitPlusNewLeafCU;
					splitCU = (splitCU > splitPlusMergeBestTwoCU) ?
					  splitCU : splitPlusMergeBestTwoCU;

					if (splitCU > bestHostCU)
					{
						bestHostCU = splitCU;
						finalBestHost = this;
						//	  tempChildren.removeElementAt(tempChildren.size()-1);
					}
					else
					{
						// restore the status quo
						mChildren = saveStatusQuo;
					}
				}

				if (finalBestHost != this)
				{
					// can commit the instance to the set of instances at this node
					mClusterInstances.Add(newInstance);
				}
				else
				{
					mCobweb.mNumberSplits++;
				}

				if (finalBestHost == merged)
				{
					mCobweb.mNumberMerges++;
					mChildren.Remove(a);
					mChildren.Remove(b);
					mChildren.Add(merged);
				}

				if (finalBestHost == newLeaf)
				{
					finalBestHost = new CNode(mNumAttributes, mCobweb);
					mChildren.Add(finalBestHost);
				}

				if (bestHostCU < mCobweb.Cutoff)
				{
					if (finalBestHost == this)
					{
						// splitting was the best, but since we are cutting all children
						// recursion is aborted and we still need to add the instance
						// to the set of instances at this node
						mClusterInstances.Add(newInstance);
					}
					mChildren = null;
					finalBestHost = null;
				}

				if (finalBestHost == this)
				{
					// splitting is still the best, so downdate the stats as 
					// we'll be recursively calling on this node
					UpdateStats(newInstance, true);
				}

				return finalBestHost;
			}

			/// <summary>
			/// Recursively assigns numbers to the nodes in the tree.
			/// </summary>
			/// <param name="clusterCount">The counts that are used recursively: the first
			/// is the number of clusters, the second is the number of leaves</param>
			internal void AssignClusterNums(int[] clusterCount)
			{
				if (mChildren != null && mChildren.Count < 2)
				{
					throw new Exception("AssignClusterNums: tree not built correctly!");
				}

				mClusterNum = clusterCount[0];
				clusterCount[0]++;
				if (mChildren != null)
				{
					for (int i = 0; i < mChildren.Count; i++)
					{
						CNode child = mChildren[i];
						child.AssignClusterNums(clusterCount);
					}
				}
				//This node is a leaf.
				else
				{
					clusterCount[1]++;
				}
			}

			#endregion

			#region Protected Internal Methods

			///<summary>
			///Adds an instance to this cluster.
			///</summary>
			///<param name="newInstance">the instance to add</param>
			protected internal void AddInstance(Instance newInstance)
			{
				// Add the instance to this cluster
				if (mClusterInstances == null)
				{
					mClusterInstances = new List<Instance>();
					mClusterInstances.Add(newInstance);
					UpdateStats(newInstance, false);
					return;
				}
				else if (mChildren == null)
				{
					/* we are a leaf, so make our existing instance(s) into a child
					   and then add the new instance as a child */
					mChildren = new List<CNode>();
					CNode tempSubCluster = new CNode(mNumAttributes,
					                                 mClusterInstances[0], mCobweb);

					//	System.out.println("Dumping "+mClusterInstances.numInstances());
					for (int i = 1; i < mClusterInstances.Count; i++)
					{
						tempSubCluster.mClusterInstances.Add(mClusterInstances[i]);
						tempSubCluster.UpdateStats(mClusterInstances[i], false);
					}

					mChildren = new List<CNode> {tempSubCluster, new CNode(mNumAttributes, newInstance, mCobweb)};

					mClusterInstances.Add(newInstance);

					UpdateStats(newInstance, false);

					// here is where we check against cutoff (also check cutoff
					// in FindHost)
					if (CategoryUtility() < mCobweb.Cutoff)
					{
						//	  System.out.println("Cutting (leaf add) ");
						mChildren = null;
					}
					return;
				}

				// otherwise, find the best host for this instance
				CNode bestHost = FindHost(newInstance, false);
				if (bestHost != null)
				{
					// now add to the best host
					bestHost.AddInstance(newInstance);
				}
			}

			/// <summary>
			/// Adds the supplied node as a child of this node. All of the child's
			/// instances are added to this nodes instances
			/// </summary>
			/// <param name="child">the child to add</param>
			protected void AddChildNode(CNode child)
			{
				for (int i = 0; i < child.mClusterInstances.Count; i++)
				{
					Instance temp = child.mClusterInstances[i];
					mClusterInstances.Add(temp);
					UpdateStats(temp, false);
				}

				if (mChildren == null)
				{
					mChildren = new List<CNode>();
				}
				mChildren.Add(child);
			}

			/// <summary>
			/// Computes the utility of all children with respect to this node
			/// </summary>
			/// <returns>the category utility of the children with respect to this node.</returns>
			protected double CategoryUtility()
			{
				if (mChildren == null)
				{
					throw new Exception("CategoryUtility: No children!");
				}

				double totalCU = 0;

				for (int i = 0; i < mChildren.Count; i++)
				{
					CNode child = mChildren[i];
					totalCU += CategoryUtilityChild(child);
				}

				totalCU /= mChildren.Count;
				return totalCU;
			}

			/// <summary>
			/// Computes the utility of a single child with respect to this node
			/// </summary>
			/// <param name="child">the child for which to compute the utility</param>
			/// <returns>the utility of the child with respect to this node</returns>
			protected double CategoryUtilityChild(CNode child)
			{

				double sum = 0;
				for (int i = 0; i < mNumAttributes; i++)
				{
					if (mCobweb.mDataSet.Attributes[i].IsNominal())
					{
						for (int j = 0; j < mCobweb.mDataSet.Attributes[i].PossibleValues.Length; j++)
						{
							double x = child.GetProbability(i, j);
							double y = GetProbability(i, j);
							sum += (x * x) - (y * y);
						}
					}
					//If it isn't nominal and it isn't numeric, then it must be a label...
					else if (mCobweb.mDataSet.Attributes[i].IsNumeric())
					{
						// numeric attribute
						sum += ((mNormal / child.GetStandardDev(i)) -
							(mNormal / GetStandardDev(i)));
					}
				}
				return (child.mTotalInstances / mTotalInstances) * sum;
			}

			/// <summary>
			/// Returns the probability of a value of a nominal attribute in this node
			/// </summary>
			/// <param name="attIndex">the index of the attribute</param>
			/// <param name="valueIndex">the index of the value of the attribute</param>
			/// <returns>the probability</returns>
			protected double GetProbability(int attIndex, int valueIndex)
			{
				if (!mCobweb.mDataSet.Attributes[attIndex].IsNominal())
				{
					throw new Exception("GetProbability: attribute is not nominal");
				}

				if (mAttStats[attIndex].TotalCount <= 0)
				{
					return 0;
				}

				return mAttStats[attIndex].NominalCounts[valueIndex] / (double)mAttStats[attIndex].TotalCount;
			}

			/// <summary>
			/// Returns the standard deviation of a numeric attribute
			/// </summary>
			/// <param name="attIndex">the index of the attribute</param>
			/// <returns>the standard deviation</returns>
			protected double GetStandardDev(int attIndex)
			{
				if (!mCobweb.mDataSet.Attributes[attIndex].IsNumeric())
				{
					throw new Exception("GetStandardDev: attribute is not numeric");
				}

				mAttStats[attIndex].NumericStats.CalculateDerived();
				double stdDev = mAttStats[attIndex].NumericStats.StdDev;
				if (double.IsNaN(stdDev) || double.IsInfinity(stdDev))
				{
					return mCobweb.Acuity;
				}

				return Math.Max(mCobweb.Acuity, stdDev);
			}

			/// <summary>
			/// Update attribute stats using the supplied instance
			/// </summary>
			/// <param name="updateInstance">the instance for updating</param>
			/// <param name="delete">true if the values of the supplied instance are
			/// to be removed from the statistics</param>
			protected internal void UpdateStats(Instance updateInstance,
						   bool delete)
			{

				if (mAttStats == null)
				{
					mAttStats = new AttributeStats[mNumAttributes];
					for (int i = 0; i < mNumAttributes; i++)
					{
						mAttStats[i] = new AttributeStats();
						if (mCobweb.mDataSet.Attributes[i].IsNominal())
						{
							mAttStats[i].NominalCounts =
							  new int[mCobweb.mDataSet.Attributes[i].PossibleValues.Length];
						}
						else
						{
							mAttStats[i].NumericStats = new Stats();
						}
					}
				}
				for (int i = 0; i < mNumAttributes; i++)
				{
					if (!updateInstance.IsValueMissing(i))
					{
						double value = updateInstance.Values[i];
						if (mCobweb.mDataSet.Attributes[i].IsNominal())
						{
							mAttStats[i].NominalCounts[(int)value] += (int)((delete)
																				?
																					(-1.0 * updateInstance.Weight)
																				:
																					updateInstance.Weight);
							mAttStats[i].TotalCount += (int)((delete) ?
							  (-1.0 * updateInstance.Weight) :
							  updateInstance.Weight);
						}
						else
						{
							if (delete)
							{
								mAttStats[i].NumericStats.Subtract(value,
												updateInstance.Weight);
							}
							else
							{
								mAttStats[i].NumericStats.Add(value, updateInstance.Weight);
							}
						}
					}
				}
				mTotalInstances += (delete)
			  ? (-1.0 * updateInstance.Weight)
			  : (updateInstance.Weight);
			}

			/// <summary>
			/// Recursively build a string representation of the Cobweb tree
			/// </summary>
			/// <param name="depth">depth of this node in the tree</param>
			/// <param name="text">holds the string representation</param>
			protected internal void DumpTree(int depth, StringBuilder text)
			{
				//If this is the root...
				if (depth == 0)
				{
					mCobweb.DetermineNumberOfClusters();
				}
				//Otherwise, this node is somewhere deeper in the tree.
				else
				{
					//Indent to the current depth
					text.Append("\r\n");
					for (int j = 0; j < depth - 1; j++)
					{
						text.Append("|   ");
					}
					//Attach this node in the correct place.
					text.Append("|---");
				}

				//If it's a leaf, write that.
				if (mChildren == null)
				{
					text.Append("leaf " + mClusterNum + " ["
							+ mClusterInstances.Count + "]");
				}
				//Otherwise, dump the node and it's children.
				else
				{
					text.Append("node " + mClusterNum + " ["
								+ mClusterInstances.Count
								+ "]");

					for (int i = 0; i < mChildren.Count; i++)
					{
						mChildren[i].DumpTree(depth + 1, text);
					}
				}
			}

			/// <summary>
			/// Returns the instances at this node as a string. Appends the cluster
			/// number of the child that each instance belongs to.
			/// </summary>
			/// <returns>a <code>String</code> value</returns>
			protected String DumpData()
			{
				if (mChildren == null)
				{
					return mClusterInstances.ToString();
				}

				// construct instances string with cluster numbers attached
				CNode tempNode = new CNode(mNumAttributes, mCobweb) {mClusterInstances = new List<Instance>()};
				for (int i = 0; i < mChildren.Count; i++)
				{
					tempNode.AddChildNode(mChildren[i]);
				}

				IDataSet tempInst = tempNode.mCobweb.mDataSet.Clone();

				String labels = "";
				for (int i = 0; i < mChildren.Count; i++)
				{
					CNode temp = mChildren[i];
					labels += ("C" + temp.mClusterNum);
					if (i < mChildren.Count - 1)
					{
						labels += ",";
					}
				}

				tempInst.Attributes.Add(DataAttribute.NewSetAttribute("Cluster",
				                                                      labels.Split(new[]
				                                                                   	{','}, StringSplitOptions.RemoveEmptyEntries)));

				int z = 0;
				for (int i = 0; i < mChildren.Count; i++)
				{
					CNode temp = mChildren[i];
					for (int j = 0; j < temp.mClusterInstances.Count; j++)
					{
						tempInst.Instances[z].Values[mNumAttributes] = i;
						z++;
					}
				}

				return tempInst.ToString();
			}

			/// <summary>
			/// Recursively generate the graph string for the Cobweb tree.
			/// </summary>
			/// <param name="text">holds the graph string</param>
			protected internal void GraphTree(StringBuilder text)
			{

				text.Append("N" + mClusterNum
					+ " [label=\"" + ((mChildren == null)
							? "leaf " : "node ")
					+ mClusterNum + " "
					+ " (" + mClusterInstances.Count
					+ ")\" "
					+ ((mChildren == null)
					  ? "shape=box style=filled " : "")
					+ (mCobweb.SaveInstances
					  ? "data =\n" + DumpData() + "\n,\n"
					  : "")
					+ "]\n");
				if (mChildren != null)
				{
					for (int i = 0; i < mChildren.Count; i++)
					{
						CNode temp = mChildren[i];
						text.Append("N" + mClusterNum
								+ "->"
								+ "N" + temp.mClusterNum
								+ "\r\n");
					}

					for (int i = 0; i < mChildren.Count; i++)
					{
						CNode temp = mChildren[i];
						temp.GraphTree(text);
					}
				}
			}

			#endregion

			#region Implementation of IProbabilisticClusterNode

			/// <summary>
			/// The instances that belong to the cluster node.
			/// </summary>
			IList<Instance> IClusterNode.Instances
			{
				get
				{
					return mClusterInstances;
				}
			}

			/// <summary>
			/// The child nodes of the current node.
			/// </summary>
			IList<IClusterNode> IClusterNode.Children
			{
				get
				{
					if (mChildren != null)
					{
						return mChildren.Select(c => (IClusterNode) c).ToList();
					}
					else
					{
						return new List<IClusterNode>();
					}
				}
			}

			/// <summary>
			/// The ID of the node.
			/// </summary>
			int IClusterNode.NodeId
			{
				get
				{
					return mClusterNum;
				}
			}

			/// <summary>
			/// Returns stats for the current node.
			/// </summary>
			/// <returns></returns>
			AttributeStats[] IProbabilisticClusterNode.GetStats()
			{
				return mAttStats;
			}

			#endregion
		}

		#endregion

		#region Public Constants/Readonly fields

		/// <summary>
		/// The default Cutoff value used by COBWEB.
		/// </summary>
		/// <remarks>
		/// This is really 0.01 * mNormal, but since fields may not be initialized
		/// in the right order, it is calculated directly here.
		/// </remarks>
		public static readonly double DefaultCutoff = 0.01 / (2 * Math.Sqrt(Math.PI));

		/// <summary>
		/// The default Acuity value used by COBWEB.
		/// </summary>
		public static readonly double DefaultAcuity = 1.0;

		#endregion

		#region Protected Fields

		///<summary>
		///Normal constant.
		///</summary>
		protected readonly static double mNormal = 1.0 / (2 * Math.Sqrt(Math.PI));

		/// <summary>
		/// Holds the root of the Cobweb tree.
		/// </summary>
		protected internal CNode mCobwebTree;

		///<summary>
		///  Number of clusters (nodes in the tree). Must never be queried directly,  only
		///  via the method <see cref="NumberOfClusters"/>. Otherwise it's not guaranteed
		///  that  it contains the correct value.
		/// <see cref="NumberOfClusters"/>,
		/// <see cref="mNumberOfClustersDetermined"/>
		///</summary>
		protected int mNumberOfClusters = -1;

		///<summary>
		///whether the number of clusters was already determined
		///</summary>
		protected bool mNumberOfClustersDetermined;

		///<summary>
		///the number of splits that happened
		///</summary>
		protected int mNumberSplits;

		///<summary>
		///the number of merges that happened
		///</summary>
		protected int mNumberMerges;

		/// <summary>
		/// The dataset being clustered.
		/// </summary>
		protected IDataSet mDataSet;

		/// <summary>
		/// The number of leaves in the dataset.
		/// </summary>
		private int mNumberOfLeaves;

		#endregion

		#region Public Properties

		///<summary>
		///Acuity (minimum standard deviation).
		///</summary>
		public double Acuity { get; set; }

		/// <summary>
		/// Cutoff (minimum category utility).
		/// </summary>
		public double Cutoff { get; set;}

		///<summary>
		/// save instance information for visualization purposes.
		/// Output instances in graph representation of Cobweb tree (Allows
		/// instances at nodes in the tree to be visualized in the Explorer).
		///</summary>
		public bool SaveInstances { get; set;}

		/// <summary>
		/// Gets or sets the DataSet being used.
		/// </summary>
		public IDataSet DataSet
		{
			get { return mDataSet; }
			set { mDataSet = value; }
		}

		/// <summary>
		/// Gets the root node.
		/// </summary>
		internal CNode Root
		{
			get 
			{
				return mCobwebTree;
			}
		}

		#endregion

		#region Public Constructors

		/// <summary>
		/// default constructor
		/// </summary>
		public Cobweb()
		{
			Cutoff = DefaultCutoff;
			Acuity = DefaultAcuity;
		}

		#endregion

		//TODO: I like this approach of classifiers and clusterers exposing their
		//		capabilities, so I may borrow it...
		//**
		// * Returns default capabilities of the clusterer.
		// *
		// * @return      the capabilities of this clusterer
		// */
		//public Capabilities getCapabilities()
		//{
		//    Capabilities result = super.getCapabilities();

		//    // attributes
		//    result.enable(Capability.NOMINAL_ATTRIBUTES);
		//    result.enable(Capability.NUMERIC_ATTRIBUTES);
		//    result.enable(Capability.DATE_ATTRIBUTES);
		//    result.enable(Capability.MISSING_VALUES);

		//    // other
		//    result.setMinimumNumberInstances(0);

		//    return result;
		//}

		#region Protected Methods

		///<summary>
		/// determines the number of clusters if necessary,
		/// <see cref="mNumberOfClusters"/>, <see cref="mNumberOfClustersDetermined"/>
		///</summary>
		protected void DetermineNumberOfClusters()
		{
			if (!mNumberOfClustersDetermined
			    && (mCobwebTree != null))
			{
				int[] clusterCounts = new int[2];
				clusterCounts[0] = 0;
				clusterCounts[1] = 0;

				try
				{
					mCobwebTree.AssignClusterNums(clusterCounts);
				}
				catch (Exception)
				{
					clusterCounts[0] = 0;
					throw;
				}

				mNumberOfClusters = clusterCounts[0];
				mNumberOfLeaves = clusterCounts[1];

				mNumberOfClustersDetermined = true;
			}
		}

		#endregion

		#region Public Methods

		///<summary>
		/// Generates the graph string of the Cobweb tree
		///</summary>
		///<returns>a <code>String</code> value</returns>
		public String Graph()
		{
			StringBuilder text = new StringBuilder();

			text.Append("digraph CobwebTree {\n");
			mCobwebTree.GraphTree(text);
			text.Append("}\n");
			return text.ToString();
		}

		///<summary>
		/// Builds the cluster tree
		///</summary>
		///<param name="data">the training instances</param>
		public void BuildClusterTree(IDataSet data)
		{
			mNumberOfClusters = -1;
			mCobwebTree = null;
			mNumberSplits = 0;
			mNumberMerges = 0;
			mDataSet = data;

			// can clusterer handle the data?
			//TODO: Re-enable this
			//getCapabilities().testWithFail(data);

			//Randomize the instance order using the Sample class.
			Sample sample = new Sample(data.Instances, true);

			while (sample.Size > 0)
			{
				Instance next = sample.SampleWithoutReplacement();

				UpdateClusterTree(next);
			}

			UpdateFinished();
		}

		///<summary>
		/// Signals the end of the updating.
		///</summary>
		public void UpdateFinished()
		{
			DetermineNumberOfClusters();
		}

		///<summary>
		/// Classifies a given instance.
		///</summary>
		///<param name="instance">the instance to be assigned to a cluster</param>
		///<returns>the number of the assigned cluster as an integer 
		/// if the class is enumerated, otherwise the predicted value</returns>
		public int ClusterInstance(Instance instance)
		{
			CNode host = mCobwebTree;
			CNode temp;

			DetermineNumberOfClusters();

			do
			{
				if (host.mChildren == null)
				{
					break;
				}

				host.UpdateStats(instance, false);
				temp = host.FindHost(instance, true);
				host.UpdateStats(instance, true);

				if (temp != null)
				{
					host = temp;
				}
			} while (temp != null);

			return host.mClusterNum;
		}

		///<summary>
		/// Returns the number of clusters.
		///</summary>
		///<returns>the number of clusters</returns>
		public int NumberOfClusters()
		{
			DetermineNumberOfClusters();
			return mNumberOfClusters;
		}

		/// <summary>
		/// Returns the number of leaves.
		/// </summary>
		/// <returns></returns>
		public int NumberOfLeaves()
		{
			DetermineNumberOfClusters();
			return mNumberOfLeaves;
		}

		///<summary>
		///Adds an instance to the cluster tree.
		///</summary>
		///<param name="newInstance">the instance to be added</param>
		public void UpdateClusterTree(Instance newInstance)
		{
			mNumberOfClustersDetermined = false;

			if (mCobwebTree == null)
			{
				mCobwebTree = new CNode(newInstance.Values.Length, newInstance, this);
			}
			else
			{
				mCobwebTree.AddInstance(newInstance);
			}
		}

		///<summary>
		///Adds an instance to the Cobweb tree.
		///</summary>
		///<param name="newInstance">the instance to be added</param>
		[Obsolete("Use UpdateClusterTree instead.")]
		public void AddInstance(Instance newInstance)
		{
			UpdateClusterTree(newInstance);
		}

		///<summary>
		///Returns a description of the cluster tree as a string
		///</summary>
		///<returns></returns>
		public override String ToString()
		{
			StringBuilder text = new StringBuilder();
			if (mCobwebTree == null)
			{
				return "Cobweb hasn't been built yet!";
			}
			else
			{
				mCobwebTree.DumpTree(0, text);
				return string.Format("Number of merges: {0}\r\nNumber of splits: {1}\r\nNumber of clusters: {2}\r\n{3}\r\n",
				                     mNumberMerges, mNumberSplits, NumberOfClusters(), text);
			}
		}

		/// <summary>
		/// Gets a string containing all the stats for all the clusters in the tree.
		/// </summary>
		/// <returns></returns>
		public string GetClusterStats()
		{
			if (mCobwebTree == null)
			{
				return "Cobweb hasn't been built yet!";
			}

			DetermineNumberOfClusters();

			StringBuilder sb = new StringBuilder();

			//Walk the cluster tree depth-first
			Stack<Pair<CNode, int>> clusterNodes = new Stack<Pair<CNode, int>>();
			clusterNodes.Push(new Pair<CNode, int>(mCobwebTree, 0));

			//Perform a depth-first walk of the cluster tree.
			while (clusterNodes.Count > 0)
			{
				Pair<CNode,int> pair = clusterNodes.Pop();
				CNode current = pair.Left;
				int depth = pair.Right;

				//This allows us to indent the output by depth.
				string padding = new string(' ', 3*depth);

				//Dump attribute stats for the cluster.
				sb.AppendFormat("{0}Cluster {1}\r\n", padding, current.mClusterNum);
				for (int i=0; i < mDataSet.Attributes.Count; i++)
				{
					DataAttribute attribute = mDataSet.Attributes[i];
					AttributeStats stats = current.mAttStats[i];

					//If it's a numeric attribute, print those stats.
					if (attribute.IsNumeric())
					{
						//Update the stats.
						stats.NumericStats.CalculateDerived();

						sb.AppendFormat("{0}-{1}: {2} [{3}]", padding, attribute.Name, stats.NumericStats.Mean, stats.NumericStats.StdDev);
					}
					else
					{
						//Otherwise, print the counts for the nomial attributes.
						sb.AppendFormat("{0}-{1}: [{2}]", padding, attribute.Name,
						                string.Join(",", stats.NominalCounts.Select(val => val.ToString()).ToArray()));
					}

					sb.AppendLine();
				}

				//Add child nodes to the stack, but do it in reverse order
				//so it will match how nodes are printed by ToString.
				if (current.mChildren != null)
				{
					for (int i=current.mChildren.Count-1; i >= 0; i--)
					{
						clusterNodes.Push(new Pair<CNode, int>(current.mChildren[i], depth + 1));
					}
				}

				sb.AppendFormat("{0}------------------\r\n", padding);
			}

			return sb.ToString();
		}

		///<summary>
		/// Returns the type of graphs this class represents.
		///</summary>
		///<returns></returns>
		public int GraphType()
		{
			//TODO:?
			throw new NotImplementedException();
			//return Drawable.TREE;
		}

		#endregion

	}
}
